package com.hy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:接雨水
 * author: Mr.Du
 * Date: 2023/6/8
 * Time: 21:21
 */
public class Trap {

    private final static int MAXIMUM_CAPACITY = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[] arr = {0,1,0,2,1,0,1,3,2,1,2,1};
        Trap trap = new Trap();
        trap.trap2(arr);
    }
    public int trap2(int[] height){
        int res = 0;
        int l = 0, r = height.length - 1;
        int lm = 0, rm = 0;
        while(l < r){
            lm = Math.max(lm, height[l]);
            rm = Math.max(rm, height[r]);
            res += lm < rm ? lm - height[l++] : rm - height[r--];
        }
        return res;
    }

    public int trap1(int[] height) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1;i < height.length;i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                int mid = stack.pop();
                if(!stack.isEmpty()){
                    res += (Math.min(height[i], height[stack.peek()]) - height[mid]) * (i - stack.peek() - 1);
                }
            }
            stack.push(i);
        }
        return res;
    }

    public static int trap(int[] height) {
        int n = height.length, res = 0;
        int[] numsL = new int[n];
        int[] numsR = new int[n];
        numsL[0] = height[0];
        numsR[n - 1] = height[n - 1];
        for(int i = 1;i < n;i++){
            numsL[i] = Math.max(height[i], numsL[i - 1]);
        }
        for(int i = n - 2;i >= 0;i--){
            numsR[i] = Math.max(height[i], numsR[i + 1]);
        }
        System.out.println(Arrays.toString(numsL));
        System.out.println(Arrays.toString(numsR));
        for(int i = 1;i < n - 1;i++){
            res += Math.min(numsL[i], numsR[i]) - height[i];
            System.out.println("height[i]: " + height[i] + ",numsL[i]: " + numsL[i] + ",numsR[i]: " + numsR[i] + ",numsR[i] - height[i]: " + (numsR[i] - height[i]) + ",res: " + res);
            System.out.println(res);
        }
        return res;
    }

}
